/**
 * https://leetcode.cn/submissions/detail/584123411/
 * 752. 打开转盘锁
 * Medium, 黄伟杰 2024.11.30
 * BFS
 */

class Solution
{ // 双向bfs
    string curup(string s, int j)
    {
        if (s[j] == '9')
            s[j] = '0';
        else
            s[j] += 1;
        return s;
    }
    string curdown(string s, int j)
    {
        if (s[j] == '0')
            s[j] = '9';
        else
            s[j] -= 1;
        return s;
    }

public:
    int openLock(vector<string> &deadends, string target)
    {
        // 用集合判断元素是否存在
        unordered_set<string> dead(deadends.begin(), deadends.end());
        unordered_set<string> q1, q2, vis;

        int step = 0; // 步数
        q1.insert("0000");
        q2.insert(target);

        while (!q1.empty() && !q2.empty())
        {
            unordered_set<string> temp;

            // 处理q1扩散
            for (auto cur : q1)
            {
                // 判断被锁的密码或是否联通
                if (dead.count(cur))
                    continue;
                if (q2.count(cur))
                    return step;

                // 防止重复
                vis.insert(cur);

                // 每个结点加减,加入下次的集合遍历
                for (int j = 0; j < 4; j++)
                {
                    string up = curup(cur, j);
                    if (!vis.count(up)) // 没走过放入
                        temp.insert(up);
                    string down = curdown(cur, j);
                    if (!vis.count(down))
                        temp.insert(down);
                }
            }
            step++; // 步数增加
            // 先起点后终点，两边一起bfs，交换集合来重复寻找，temp是上一次结点bfs后的结点
            q1 = q2;
            q2 = temp;
        }
        return -1;
    }
};